#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/12/3 16:43|16:43
# @Author  : yangdingyi
# @File    : 反转链表
# @Software: PyCharm


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 1.递推
        # h, p = None, head
        # while p:
        #     q = p.next
        #     p.next = h
        #     h = p
        #     p = q
        # return h
        # 2.递归
        def work(p: ListNode) -> ListNode:
            if not p:
                return None
            q = work(p.next)
            if q:
                q.next = p
            return p


def display(head: ListNode) -> None:
    p = head
    data = []
    while p:
        data.append(str(p.val))
        p = p.next
    print('->'.join(data))


data = [1, 2, 3, 4, 5]
solve = Solution()
head = None
while data:
    a = data.pop()
    if not head:
        head = ListNode(a)
    else:
        p = ListNode(a)
        p.next = head
        head = p

display(head)
display(solve.reverseList(head))






